package leetcode_core.leetcode_4;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年10月28日 8:53
 */
public class SumSubarrayMins {
    //求解一个列表,这个列表定义
    //对于nums[i],找到一个nums[left]是第一个比它小的,找到一个nums[right]是第一个比它小的
    //定义arr[i][2]={left,right}
    static final int  mod = (int)(1e9+7);
    public int sumSubarrayMins(int[] nums) {
        int n = nums.length;
        int[][] arr = new int[nums.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        long result = 0;
        //单调栈处理
        for(int i = 0;i < n;i++){
            //其关键是对于左边相等的数要如何进行处理
            while(!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]){
                //那么就结算当前的peek()
                List<Integer> peek = stack.pop();
                int size = peek.size();
                for(int j = 0;j< size; j++){
                    int left = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
                    int idx = peek.get(j);
                    if(j == 0){
                        arr[idx][0] = left;//左边这个元素
                    }else{
                        arr[idx][0] = peek.get(0);//与前面那个元素相等
                    }
                    arr[idx][1] = i;
                    result = (result + 1L*(arr[idx][1] - idx)*(idx - arr[idx][0])*nums[idx])%mod;
                }
            }
            if(!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]){
                stack.peek().add(i);
            }else{
                ArrayList<Integer> v = new ArrayList<>();
                v.add(i);
                stack.push(v);
            }
        }
        //如果到最后栈都还没空,那么这时候就要手动清空
        while (!stack.isEmpty()){
            List<Integer> peek = stack.pop();
            int size = peek.size();
            int left = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
            for(int i = 0;i<size;i++){
                int idx = peek.get(i);
                if(i == 0){
                    arr[idx][0] = left;
                }else{
                    arr[idx][0] = peek.get(0);
                }
                arr[idx][1] = nums.length;
                result = (result + 1L*(arr[idx][1] - idx)*(idx - arr[idx][0])*nums[idx])%mod;
            }
        }
        for(int i = 0;i< nums.length;i++){
            System.out.print(i+":"+nums[i]+" ");
        }
        System.out.println();
        for(int i = 0;i<n;i++){
            System.out.println("i:"+i+",nums[i]="+nums[i]+",left:"+arr[i][0]+",right:"+arr[i][1]);
        }
        //然后结算即可
        System.out.println(result);
        return (int)result;
    }
    @Test
    public void test(){
        sumSubarrayMins(new int[]{3,3,2,4});
    }
}
